// 解数独
/*编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解
*/
class Solution {
    bool row[9][10] = {0};
    bool col[9][10] = {0};
    bool dig[3][3][10] = {0};

public:
    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int temp = board[i][j] - '0';
                    row[i][temp] = col[j][temp] = dig[i / 3][j / 3][temp] =
                        true;
                }
            }
        }
        dfs(board);
    }
    bool dfs(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (int k = 1; k <= 9; k++) {
                        if (!row[i][k] && !col[j][k] && !dig[i / 3][j / 3][k]) {
                            row[i][k] = col[j][k] =
                                dig[i / 3][j / 3][k] = true;
                            board[i][j] = k + '0';
                            if (dfs(board))
                                return true;
                            row[i][k] = col[j][k] =
                                dig[i / 3][j / 3][k] = false;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
};


//单词搜索
/*给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
*/
class Solution {
    bool dig[7][7] = {0};
    int count = 0;
    int row[4] = {0, 0, 1, -1};
    int col[4] = {1, -1, 0, 0};

public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (word[0] == board[i][j])
                    if (dfs(board, i, j, word, 0))
                        return true;
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board, int x, int y, string& word, int pos) {
        if (board[x][y] == word[pos]) {
            count++;
            dig[x][y] = true;
            if (count == word.size())
                return true;
            for (int i = 0; i < 4; i++) {
                if (x + row[i] < board.size() && y + col[i] < board[0].size() &&
                    !dig[x + row[i]][y + col[i]]) {
                    if (dfs(board, x + row[i], y + col[i], word, pos + 1))
                        return true;
                }
            }
            count--;
            dig[x][y] = false;
        }
        return false;
    }
};